import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-26
 * Time: 10:20
 */
public class Solution {
    public boolean isBipartite(int[][] graph) {
        int counts = graph.length;
        // 0 代表未涂 , 用 1 代表其中一个颜色, 2 代表另一个颜色
        int[] colors = new int[counts];
        Queue<Integer> queue = new LinkedList<>();
        // 外层 for 循环用来找不同的连通分支
        for (int i = 0; i < counts; i++) {
            if (colors[i] == 0){
                colors[i] = 1;
                queue.add(i);
                while (!queue.isEmpty()){
                    int node = queue.poll();
                    for (int j = 0; j < graph[node].length; j++) {
                        int near = graph[node][j];
                        // 相邻两个节点颜色相同, 则为 false
                        if (colors[near] == colors[node]){
                            return false;
                        }
                        // 只有这个相邻节点还没有被涂色时才加入到队列中
                        if (colors[near] == 0){
                            queue.add(near);
                        }
                        // 相邻节点涂不同的颜色
                        colors[near] = colors[node] == 1 ? 2 : 1;
                    }
                }
            }
        }
        return true;
    }
}